package lianxi;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2023-03-13
 * Time: 19:22
 */

/**
 * 回文串分割:
 * 给出一个字符串s，分割s使得分割出的每一个子串都是回文串
 * 计算将字符串s分割成回文分割结果的最小切割数
 * 例如:给定字符串s="aab",
 * 返回1，因为回文分割结果["aa","b"]是切割一次生成的。
 * 思路: 动态规划
 *   问题: 求将s分割为每一段都是回文串的的最小分割数
 *   子问题: 将s的一部分分割为回文串的次数
 *   状态:  将s的前i个字符分割为回文串的最小次数
 *   分析: 举例 aab, 初始状态1个字符的时候不需要分割, F[1] = 0, F[2] = 0(已经是回文串), F[3]=min(F[j])+1
 *   状态转移方程:
 *     1. 已经是回文串 F[i]=0
 *     2. if(j<i && s[j+1,i]是回文串) F[i] = min(F[j])+1
 */
public class Solution {

    public boolean isPal(String s, int start, int end){
        while(start<end){
            if(s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public int minCut (String s) {
        if(s.length() == 0) return 0;
        int []minc = new int[s.length()+1];
        int len = s.length();
        //初始化, 每种状态的最大分割数为 i-1;
        for(int i=1; i<=len;i++){
            minc[i] = i-1;
        }
        for(int i=2; i<=len; i++){
            if(isPal(s, 0, i-1)) {
                minc[i] = 0;
                continue;
            }
            for(int j=0; j<i; j++){
                if(isPal(s, j, i-1)){
                    minc[i] = Math.min(minc[j]+1, minc[i]);
                }
            }
        }
        return minc[len];
    }
}
